package leetcode;

public class BitwiseANDNumbersRange {

	public static void main(String[] args) {
		int m = 5; 
		int n = 5;
		BitwiseANDNumbersRange object = new BitwiseANDNumbersRange();
		System.out.println(object.rangeBitwiseAnd(m, n));
	}
	
	// 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range
	
	//如果m和n的做左边的1的位数不一样，那么结果就是0
	//比如100 ~ 1000，按位与肯定是0;
	public int rangeBitwiseAnd(int m, int n) {
        int[] bitsOfM = new int[32];
        int[] bitsOfN = new int[32];
        int onePosM = 0,  onePosN = 0;
        for(int i = 0; i < 32; i++){
        	int bitM = (m & 1);
        	bitsOfM[i] = bitM;
        	if(bitM == 1){
        		onePosM = i;
        	}
        	m >>>= 1;
        	int bitN = (n & 1);
        	bitsOfN[i] = bitN;
        	if(bitN == 1){
        		onePosN = i;
        	}
        	n >>>= 1;
        }
        //如果最左边的1的位置不一样，那么可以直接返回0
        if(onePosM != onePosN){
        	return 0;
        }
        System.out.println("onePosM: " + onePosM);
        int res = 0;
        for (int i = onePosM; i >= 0; i--) {
			if(bitsOfM[i] == 1 && bitsOfN[i] == 1){
				res += 1 << i;
			}else if(bitsOfM[i] + bitsOfN[i] == 1){
				//一个为0， 一个为1，就break
				break;
			}
		}
        return res;
    }
}
